let arr = [
    { id: 1, name: '部门1', pid: 0 },
    { id: 2, name: '部门2', pid: 1 },
    { id: 3, name: '部门3', pid: 1 },
    { id: 4, name: '部门4', pid: 3 },
    { id: 5, name: '部门5', pid: 4 },
    { id: 6, name: '部门6', pid: 0 },
]
//? O(n2)
function List2Tree(arr) {
    let res = []
    arr.forEach((item,index) => {
        //? 搜索此item的孩子
        const kids = arr.filter(child => {
            return child.pid === item.id
        })
        //? 有孩子可以加了
        if (kids.length > 0) {
            item.children = kids
        }
        //? 这个节点不是孩子 置入最外层
        if (item.pid === 0) {
            res.push(item)
        }
    })
    return res
}
console.log(List2Tree(arr));

//? O(n) 思路是把孩子加给父 父存在map中
function betterList2Tree(arr) {
    const list = [];
    const hashmap = {};
    for (let i = 0; i < arr.length; i++) {
        //? 存储每个id下的子元素
        let pid = arr[i].pid
        let id = arr[i].id
        //? 添加此id入map
        if (!hashmap[id]) {
            //? 每一个都添加一个children
            hashmap[id] = {
                children:[]
            }
        }
        //? 自己肯定要加进去啊 这里这样操作为了避免孩子已经入了才轮到父处理的情况
        hashmap[id] = {...arr[i], children:hashmap[id].children}
        //? 此节点是父
        if (pid === 0) {
            list.push(hashmap[id]);
        }
        else {
            //? 找父 此时存在父还没遍历到的情况
            if (!hashmap[pid]) {
                hashmap[pid] = {
                    children:[]
                }
            }
            hashmap[pid].children.push(hashmap[id])
        }
    }
    return list;
}

console.log(betterList2Tree(arr));
